SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Algorithme d'approximation</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Algorithme d'approximation</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="fr" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="fr" dir="ltr"><p>En <a href="Informatique_th%C3%A9orique" title="Informatique théorique">informatique théorique</a>, un <b>algorithme d'approximation</b> est une méthode permettant de calculer une solution approchée à un problème <a href="Algorithmique" title="Algorithmique">algorithmique</a> d'<a href="Optimisation_(math%C3%A9matiques)" title="Optimisation (mathématiques)">optimisation</a>. Plus précisément, c'est une <a href="Heuristique_(math%C3%A9matiques)" title="Heuristique (mathématiques)">heuristique</a> garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.

</p><p>L'intérêt de tels algorithmes est qu'il est parfois plus facile de trouver une solution approchée qu'une solution exacte, le problème pouvant par exemple être <a href="NP-complet" class="mw-redirect" title="NP-complet">NP-complet</a> mais admettre un algorithme d'approximation polynomial. Ainsi, dans les situations où l'on cherche une bonne solution, mais pas forcément la meilleure, un algorithme d'approximation peut être un bon outil.

</p>

<div class="mw-heading mw-heading2"><h2 id="Définitions"><span id="D.C3.A9finitions"></span>Définitions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Approximation">Approximation</h3></div>

<p>Selon la nature du problème (maximisation, <a href="Optimisation_(math%C3%A9matiques)" title="Optimisation (mathématiques)">minimisation</a>, etc.) la définition peut varier, on donne ici la définition classique pour un problème de minimisation avec facteur d'<a href="Approximation" title="Approximation">approximation</a> constant.

</p><p>Pour un problème de minimisation ayant une solution optimale de valeur <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a5b376dccffe5ae946dcdb7e98bf41beae28dc9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.343ex;" alt="{\displaystyle z^{*}}" loading="lazy"></span>, un algorithme d'approximation de facteur <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho >1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho >1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/583ebbd6b4f4899a073bb9b1360d8d5f0cd27bf0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.463ex; height:2.676ex;" alt="{\displaystyle \rho >1}" loading="lazy"></span> (i.e. un <b>algorithme <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1f7d439671d1289b6a816e6af7a304be40608d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }" loading="lazy"></span>-approché</b>) est un algorithme donnant une solution de valeur <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"></span>, avec la garantie que <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\leq \rho z^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\leq \rho z^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9979f36a45d8b168ea6419ec847d3125986c88ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.533ex; height:2.843ex;" alt="{\displaystyle z\leq \rho z^{*}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Schéma_d'approximation"><span id="Sch.C3.A9ma_d.27approximation"></span>Schéma d'approximation</h3></div>

<p>Un schéma d'approximation est un algorithme prenant comme entrée les données du problèmes mais aussi une valeur <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon >0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/568095ad3924314374a5ab68fae17343661f2a71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;" alt="{\displaystyle \epsilon >0}" loading="lazy"></span> et calculant une solution approchée avec un facteur <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1+\epsilon )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1+\epsilon )}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/18f8e2d8b0403799b0fb1cf5ff2992466aae1fcb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.756ex; height:2.843ex;" alt="{\displaystyle (1+\epsilon )}" loading="lazy"></span>. Si le temps de calcul est polynomial en la taille de l'entrée pour chaque valeur <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy"></span>, on parle de <a href="Sch%C3%A9ma_d'approximation_en_temps_polynomial" title="Schéma d'approximation en temps polynomial">schéma d'approximation en temps polynomial</a> (abrégé <i>PTAS</i> en anglais). Si de plus, on demande que le temps de calcul soit aussi polynomial en <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/\epsilon }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/\epsilon }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/656e71e33c17e6e344d005ee2fadfed2d4f2a7b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.269ex; height:2.843ex;" alt="{\displaystyle 1/\epsilon }" loading="lazy"></span>, on parle de <a href="Sch%C3%A9ma_d'approximation_en_temps_enti%C3%A8rement_polynomial" title="Schéma d'approximation en temps entièrement polynomial">schéma d'approximation en temps entièrement polynomial</a> (abrégé <i>FPTAS</i> en anglais)<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Exemple">Exemple</h2></div>

<p>Par exemple pour le problème du <a href="Th%C3%A9or%C3%A8me_de_K%C3%B6nig_(th%C3%A9orie_des_graphes)" class="mw-redirect" title="Théorème de König (théorie des graphes)">transversal minimum</a> puisque tout transversal formé par les sommets incidents aux arêtes d'un couplage maximal pour l'inclusion a une cardinalité inférieure à deux fois l'optimum.

</p><p>C'est aussi le cas pour le cas particulier du <a href="Probl%C3%A8me_du_voyageur_de_commerce" title="Problème du voyageur de commerce">voyageur de commerce</a> où les poids satisfont les inégalités triangulaires car alors, le poids minimum d'un <a href="Algorithme_de_Kruskal" title="Algorithme de Kruskal">arbre couvrant</a> est toujours inférieur à deux fois l'optimum. En affinant cette approche en utilisant un <a href="Couplage_(th%C3%A9orie_des_graphes)" title="Couplage (théorie des graphes)">couplage</a> bien choisi on peut aussi obtenir un facteur d'approximation de 3/2, avec l'<a href="Algorithme_de_Christofides" title="Algorithme de Christofides">algorithme de Christofides</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Techniques_algorithmiques">Techniques algorithmiques</h2></div>

<p>Parmi les techniques utilisées<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>, on compte les méthodes d'algorithmique classique, par exemple un <a href="Algorithme_glouton" title="Algorithme glouton">algorithme glouton</a> permet parfois d'obtenir une bonne approximation à défaut de calculer une solution optimale. On peut aussi citer des algorithmes de <a href="Recherche_locale_(optimisation)" title="Recherche locale (optimisation)">recherche locale</a> et de <a href="Programmation_dynamique" title="Programmation dynamique">programmation dynamique</a>.

</p><p>Beaucoup d'algorithmes sont basées sur l'<a href="Optimisation_lin%C3%A9aire" title="Optimisation linéaire">optimisation linéaire</a>. On peut par exemple arrondir une solution fractionnaire ou utiliser un schéma primal-dual. Une technique plus avancée est d'utiliser l'<a href="Optimisation_SDP" title="Optimisation SDP">optimisation SDP</a>, comme pour le <a href="Probl%C3%A8me_de_la_coupe_maximum" class="mw-redirect" title="Problème de la coupe maximum">problème de la coupe maximum</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Difficulté_d'approximation"><span id="Difficult.C3.A9_d.27approximation"></span>Difficulté d'approximation</h2></div>

<p>Parmi les problèmes <a href="NP-complet" class="mw-redirect" title="NP-complet">NP-complets</a> certains sont dits <i>difficile à approximer</i>, c'est-à-dire qu'ils n'admettent pas d'algorithme d'approximation si l'on suppose certaines hypothèses, par exemple <a href="Probl%C3%A8me_P%3DNP" class="mw-redirect" title="Problème P=NP">P différent de NP</a> ou bien la <a href="Conjecture_des_jeux_uniques" title="Conjecture des jeux uniques">conjecture des jeux uniques</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Exemples_simples">Exemples simples</h3></div>

<p>Le <a href="Probl%C3%A8me_du_voyageur_de_commerce" title="Problème du voyageur de commerce">problème du voyageur de commerce</a> dans un graphe <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"></span> avec des poids quelconques (positifs) est un problème qui n'admet pas d'algorithme d'approximation. En effet, tout algorithme d'approximation pour ce problème dans le graphe complet <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{V}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{V}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dc112200e1a1c18ff1e0aaba8bb83a17b54ac529.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.469ex; height:2.509ex;" alt="{\displaystyle K_{V}}" loading="lazy"></span> où les arêtes de <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span> ont une valeur nulle et les autres la valeur 1 fournit une réponse au problème de décision <a href="NP-complet" class="mw-redirect" title="NP-complet">NP-complet</a> de statuer sur l'<a href="Graphe_hamiltonien" title="Graphe hamiltonien">hamiltonicité</a> d'un graphe (en l'occurrence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> est hamiltonien si et seulement si l'algorithme approché fournit une solution de valeur nulle).

</p><p>Un autre problème est le <a href="Probl%C3%A8me_du_k-centre_m%C3%A9trique" class="mw-redirect" title="Problème du k-centre métrique">problème du k-centre métrique</a> qui admet une réduction simple au <a href="Probl%C3%A8me_de_l'ensemble_dominant" class="mw-redirect" title="Problème de l'ensemble dominant">problème de l'ensemble dominant</a><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Techniques_avancées"><span id="Techniques_avanc.C3.A9es"></span>Techniques avancées</h3></div>

<p>Il existe des techniques plus complexes pour montrer des résultats de difficulté d'approximation. Elles tournent essentiellement autour du <a href="Th%C3%A9or%C3%A8me_PCP" title="Théorème PCP">théorème PCP</a>.

Plus récemment la <a href="Conjecture_des_jeux_uniques" title="Conjecture des jeux uniques">conjecture des jeux uniques</a> a été utilisée pour montrer des résultats plus forts.

</p>

<div class="mw-heading mw-heading2"><h2 id="Historique">Historique</h2></div>

<p>Des algorithmes d'approximation ont été découverts avant même la mise en place de la théorie de la NP-complétude<sup id="cite_ref-vazirani_4-0" class="reference"><a href="#cite_note-vazirani-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>, par exemple par <a href="Paul_Erd%C5%91s" title="Paul Erdős">Paul Erdős</a> dans les années 1960, pour le <a href="Coupe_maximum" title="Coupe maximum">problème de la coupe maximum</a><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> ou <a href="Ronald_Graham" title="Ronald Graham">Ronald Graham</a>, pour les algorithmes d'ordonnancement

. Cependant c'est à la suite de cette théorie que le domaine s'est vraiment développé<sup id="cite_ref-vazirani_4-1" class="reference"><a href="#cite_note-vazirani-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>. L'utilisation de l'<a href="Optimisation_lin%C3%A9aire" title="Optimisation linéaire">optimisation linéaire</a> est due à <a href="L%C3%A1szl%C3%B3_Lov%C3%A1sz" title="László Lovász">László Lovász</a> dans les années 1970<sup id="cite_ref-vazirani_4-2" class="reference"><a href="#cite_note-vazirani-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>, pour le <a href="Probl%C3%A8me_de_couverture_par_ensembles" title="Problème de couverture par ensembles">problème de couverture par ensembles</a><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>.

</p><p>Dans les années 1990, le <a href="Th%C3%A9or%C3%A8me_PCP" title="Théorème PCP">théorème PCP</a> a été une avancée très importante pour la non-approximabilité.

</p>

<div class="mw-heading mw-heading2"><h2 id="Notes_et_références"><span id="Notes_et_r.C3.A9f.C3.A9rences"></span>Notes et références</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Cormen2fr"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. <span class="nom_auteur">Cormen</span></a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. <span class="nom_auteur">Leiserson</span></a>, <a href="Ronald_Rivest" title="Ronald Rivest">Ronald L. <span class="nom_auteur">Rivest</span></a> et <a href="Clifford_Stein" title="Clifford Stein">Clifford <span class="nom_auteur">Stein</span></a>, <cite class="italique"><a href="Introduction_%C3%A0_l'algorithmique" title="Introduction à l'algorithmique">Introduction à l'algorithmique</a></cite>, <a href="Dunod" class="mw-redirect" title="Dunod">Dunod</a>, <time>2002</time> <small>[détail de l’édition]</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+%C3%A0+l%27algorithmique&rft.pub=Dunod&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rft.au=Stein%2C+Clifford&rft.date=2002&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+d%27approximation"></span></span>, chap. 35.</span>

</li>

<span class="ouvrage" id="WilliamsonShmoys"><span class="ouvrage" id="David_P._WilliamsonDavid_B._Shmoys"><a href="David_P._Williamson" title="David P. Williamson">David P. Williamson</a> et David B. Shmoys, <cite class="italique">The Design of Approximation Algorithms</cite>, <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.designofapproxalgs.com/">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Design+of+Approximation+Algorithms&rft.pub=Cambridge+University+Press&rft.aulast=Williamson&rft.aufirst=David+P.&rft.au=David+B.+Shmoys&rft_id=http%3A%2F%2Fwww.designofapproxalgs.com%2F&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+d%27approximation"></span></span></span></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a> </span><span class="reference-text">Voir <span class="ouvrage" id="Vazirani_2001"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="Vijay_Vazirani" title="Vijay Vazirani">Vijay <span class="nom_auteur">Vazirani</span></a>, <cite class="italique" lang="en">Approximation algorithms</cite>, <a href="Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>, 2001 (puis 2003), 380 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <span class="nowrap">978-3-540-65367-7</span>)</small>, <abbr class="abbr" title="chapitre(s)">chap.</abbr> 5<span class="lang-en" lang="en"> (« k-center »)</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Approximation+algorithms&rft.atitle=k-center&rft.pub=Springer+Verlag&rft.aulast=Vazirani&rft.aufirst=Vijay&rft.date=2003&rft.tpages=380&rft.isbn=978-3-540-65367-7&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+d%27approximation"></span></span></span>

</li>

<li id="cite_note-vazirani-4"><span class="reference-text"><span class="ouvrage" id="Vazirani_2001"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="Vijay_Vazirani" title="Vijay Vazirani">Vijay <span class="nom_auteur">Vazirani</span></a>, <cite class="italique" lang="en">Approximation algorithms</cite>, <a href="Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>, 2001 (puis 2003), 380 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <span class="nowrap">978-3-540-65367-7</span>)</small>, <abbr class="abbr" title="chapitre(s)">chap.</abbr> 1.4<span class="lang-en" lang="en"> (« Introduction : Notes »)</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Approximation+algorithms&rft.atitle=Introduction+%3A+Notes&rft.pub=Springer+Verlag&rft.aulast=Vazirani&rft.aufirst=Vijay&rft.date=2003&rft.tpages=380&rft.isbn=978-3-540-65367-7&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+d%27approximation"></span></span> p. 10.</span>

</li>

<span class="ouvrage" id="Erdős1967"><span class="ouvrage" id="Paul_Erdős1967">Paul Erdős, « <cite style="font-style:normal">Gráfok páros körüljárású részgráfjairól (On bipartite subgraphs of graphs, in Hungarian),</cite> », <i>Mat. Lapok</i>, <abbr class="abbr" title="volume">vol.</abbr> 18,‎ <time>1967</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">283-288</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Gr%C3%A1fok+p%C3%A1ros+k%C3%B6r%C3%BClj%C3%A1r%C3%A1s%C3%BA+r%C3%A9szgr%C3%A1fjair%C3%B3l+%28On+bipartite+subgraphs+of+graphs%2C+in+Hungarian%29%2C&rft.jtitle=Mat.+Lapok&rft.aulast=Erd%C5%91s&rft.aufirst=Paul&rft.date=1967&rft.volume=18&rft.pages=283-288&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+d%27approximation"></span></span></span></span>

</li>

<span class="ouvrage" id="Graham1966"><span class="ouvrage" id="R._L._Graham1966">R. L. <span class="nom_auteur">Graham</span>, « <cite style="font-style:normal">Bounds for certain multiprocessing anomalies</cite> », <i><a href="Bell_System_Technical_Journal" title="Bell System Technical Journal">Bell System Technical Journal</a></i>, <abbr class="abbr" title="volume">vol.</abbr> 45, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 9,‎ <time>1966</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">1563–1581</span> <small style="line-height:1em;">(<a href="Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <span class=" noarchive nowrap"><a rel="nofollow" class="external text" href="https://dx.doi.org/10.1002/j.1538-7305.1966.tb01709.x">10.1002/j.1538-7305.1966.tb01709.x</a></span>, <a rel="nofollow" class="external text" href="http://www.math.ucsd.edu/~ronspubs/66_04_multiprocessing.pdf">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Bounds+for+certain+multiprocessing+anomalies&rft.jtitle=Bell+System+Technical+Journal&rft.issue=9&rft.aulast=Graham&rft.aufirst=R.+L.&rft.date=1966&rft.volume=45&rft.pages=1563%E2%80%931581&rft_id=info%3Adoi%2F10.1002%2Fj.1538-7305.1966.tb01709.x&rft_id=http%3A%2F%2Fwww.math.ucsd.edu%2F~ronspubs%2F66_04_multiprocessing.pdf&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+d%27approximation"></span></span></span></span>

</li>

<span class="ouvrage" id="Graham1969"><span class="ouvrage" id="R._L._Graham1969">R. L. <span class="nom_auteur">Graham</span>, « <cite style="font-style:normal">Bounds on multiprocessing timing anomalies</cite> », <i><a href="SIAM_Journal_on_Applied_Mathematics" title="SIAM Journal on Applied Mathematics">SIAM Journal on Applied Mathematics</a></i>, <abbr class="abbr" title="volume">vol.</abbr> 17,‎ <time>1969</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">416–429</span> <small style="line-height:1em;">(<a href="Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <span class=" noarchive nowrap"><a rel="nofollow" class="external text" href="https://dx.doi.org/10.1137/0117039">10.1137/0117039</a></span>, <a href="Mathematical_Reviews" title="Mathematical Reviews">MR</a> <span class=" noarchive nowrap"><a rel="nofollow" class="external text" href="https://www.ams.org/mathscinet-getitem?mr=249214">249214</a></span>, <a rel="nofollow" class="external text" href="https://www.math.ucsd.edu/~ronspubs/69_02_multiprocessing.pdf">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Bounds+on+multiprocessing+timing+anomalies&rft.jtitle=SIAM+Journal+on+Applied+Mathematics&rft.aulast=Graham&rft.aufirst=R.+L.&rft.date=1969&rft.volume=17&rft.pages=416%E2%80%93429&rft_id=info%3Adoi%2F10.1137%2F0117039&rft_id=https%3A%2F%2Fwww.math.ucsd.edu%2F~ronspubs%2F69_02_multiprocessing.pdf&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+d%27approximation"></span></span></span></span>

</li>

<span class="ouvrage" id="Lovász1975"><span class="ouvrage" id="László_Lovász1975">László Lovász, « <cite style="font-style:normal">On the ratio of optimal integral and fractional covers</cite> », <i>Discrete mathematics</i>, <abbr class="abbr" title="volume">vol.</abbr> 13, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 4,‎ <time>1975</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">383-390</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=On+the+ratio+of+optimal+integral+and+fractional+covers&rft.jtitle=Discrete+mathematics&rft.issue=4&rft.aulast=Lov%C3%A1sz&rft.aufirst=L%C3%A1szl%C3%B3&rft.date=1975&rft.volume=13&rft.pages=383-390&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AAlgorithme+d%27approximation"></span></span></span></span>

</li>

</ol></div>

<ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"></span></span> <span class="bandeau-portail-texte">Portail de l'informatique théorique</span> </span></li> </ul></div><div><div class="zim-footer">

Cet article est issu de <a class="external text" title="Dernière modification le 2025-07-21" href="https://fr.wikipedia.org/wiki/?title=Algorithme_d'approximation&oldid=227458744">Wikipédia</a>. Sauf mention contraire, le texte est disponible sous <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">Creative Commons Attribution-Share Alike 4.0</a>. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

</div>

</div></div>

</div>

</main>

</div>

</body></html>